﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Collections.ObjectModel;
using System.Diagnostics;
using System.Linq;
using System.Text;

namespace JasLib.Extensions
{
    public static class EmptyEnumerable<T>
    {
        /// <summary>
        /// Empty arrays are common and immutable, so this helps the programmer "intern" them.
        /// </summary>
        public static readonly T[] EmptyArray = new T[0];
    }

    /// <summary>
    /// </summary>
    public static class ListExtensions
    {
        /**********************************************************************************/
        public static void AddRange(this IList thisList, params object[] newItemArray)
        {
            AddRange(thisList, newItemArray as IEnumerable);
            return;
        }

        /**********************************************************************************/
        public static void AddRange(this IList thisList, IEnumerable newItems)
        {
            foreach (object value in newItems)
                thisList.Add(value);
            return;
        }

        /**********************************************************************************/
        public static void AddRange<T>(this IList<T> thisList, params T[] newItemArray)
        {
            thisList.AddRange(newItemArray as IEnumerable<T>);
            return;
        }

        /**********************************************************************************/
        /// <summary>
        /// Matches the functionality built into List&lt;T&gt;.
        /// </summary>
        public static void AddRange<T>(this IList<T> thisList, IEnumerable<T> newItems)
        {
            foreach (T value in newItems)
                thisList.Add(value);
            return;
        }

        /**********************************************************************************/
        /// <summary>
        /// Creates an array from the enumerable, simply casting the object reference if it already is one.
        /// </summary>
        public static T[] AsArray<T>(this IEnumerable<T> source)
        {
            if (source == null)
                return null;
            else
            {
                /// We don't need to pre-optimize ToArray() further; internally it already checks if the source
                /// is a collection and then uses the interface's CopyTo() override to quickly write to the array.
                T[] result = (source as T[]) ?? source.ToArray();

                /// Immediately submit the result to the GC and return instead a static readonly empty array.
                if (result.Length == 0)
                    return EmptyEnumerable<T>.EmptyArray;

                return result;
            }
        }

        /**********************************************************************************/
        public static ArrayList AsArrayList(this IEnumerable source)
        {
            if (source is ArrayList)
                return (source as ArrayList);
            else
            {
                ArrayList newList = new ArrayList();
                newList.AddRange(source);
                return newList;
            }
        }

        /**********************************************************************************/
        /// <summary>
        /// Creates a List&lt;T&gt; from the enumerable, simply casting the object reference if it already is one.
        /// </summary>
        public static List<T> AsList<T>(this IEnumerable<T> source)
        {
            if (source == null)
                return null;
            else
            {
                /// We don't need to pre-optimize ToList() further; internally it already checks if the source
                /// is a collection and then uses the interface's CopyTo() override to quickly write to the list's
                /// internal array.
                return (source as List<T>) ?? source.ToList();
            }
        }

        /**********************************************************************************/
        /// <summary>
        /// Creates an observable collection from the enumerable, simply casting the object reference if it already is one.
        /// </summary>
        public static ObservableCollection<T> AsObservableCollection<T>(this IEnumerable<T> source)
        {
            if (source == null)
                return null;
            else
                return (source as ObservableCollection<T>) ?? new ObservableCollection<T>(source);
        }

        #region Binary search

        /**********************************************************************************/
        /// <summary>
        /// </summary>
        public static int BinarySearch<T>(
            this IList<T> list,
            Func<T, int> func,
            int iStart = 0,
            int iCount = -1)
        {
            /// Hardcoded for now.
            if (iCount == -1)
                iCount = list.Count;

            /// Swiped from <seealso cref="System.Collections.Generic.ArraySortHelper&lt;T&gt;"/>.
            int iSpanFirst = iStart;
            int iSpanLast = (iStart + iCount) - 1;
            while (iSpanFirst <= iSpanLast)
            {
                int iIndex = iSpanFirst + ((iSpanLast - iSpanFirst) >> 1);
                int iComparison = func(list[iIndex]);
                if (iComparison == 0)
                {
                    return iIndex;
                }
                else if (iComparison < 0)
                {
                    iSpanFirst = iIndex + 1;
                }
                else
                {
                    iSpanLast = iIndex - 1;
                }
            }
            return ~iSpanFirst;
        }

        /**********************************************************************************/
        public static int BinarySearch<TSource, TKey>(
            this IList<TSource> list,
            Func<TSource, TKey> func,
            TSource value)
        {
            Comparison<TKey> comparison = new Comparison<TKey>(Comparer<TKey>.Default.Compare);
            TKey key = func(value);
            return BinarySearch(list, t => comparison(func(t), key));
        }

        /**********************************************************************************/
        public static int BinarySearch<T>(
            this IList<T> list,
            T value)
        {
            Comparison<T> comparison = new Comparison<T>(Comparer<T>.Default.Compare);
            return BinarySearch(list, t => comparison(t, value));
        }

        /**********************************************************************************/
        internal static int BinarySearch_ConvertResultToInsertionIndex(int iListCount, int iIndex)
        {
            if (iIndex == -1)
                return 0;
            else if (iIndex == -(iListCount + 1))
                return iListCount;
            else if (iIndex < 0)
                return (-iIndex - 1);
            else
                return iIndex;
        }

        /**********************************************************************************/
        public static void BinarySearchInsert<T>(
            this IList<T> list,
            T value)
        {
            int iIndex = BinarySearch(list, value);
            iIndex = BinarySearch_ConvertResultToInsertionIndex(list.Count, iIndex);
            list.Insert(iIndex, value);
            return;
        }

        /**********************************************************************************/
        public static void BinarySearchInsert<TSource, TKey>(
            this IList<TSource> list,
            Func<TSource, TKey> func,
            TSource value)
        {
            Comparison<TKey> comparison = new Comparison<TKey>(Comparer<TKey>.Default.Compare);
            TKey key = func(value);

            int iIndex = BinarySearch(list, t => comparison(func(t), key));
            iIndex = BinarySearch_ConvertResultToInsertionIndex(list.Count, iIndex);
            list.Insert(iIndex, value);
            return;
        }

        /**********************************************************************************/
        public static int BinarySearchDescending<T>(
            this IList<T> list,
            T value)
        {
            Comparison<T> comparison = new Comparison<T>(Comparer<T>.Default.Compare);
            return BinarySearch(list, t => -comparison(t, value));
        }

        /**********************************************************************************/
        public static void BinarySearchInsertDescending<T>(
            this IList<T> list,
            T value)
        {
            int iIndex = BinarySearchDescending(list, value);
            iIndex = BinarySearch_ConvertResultToInsertionIndex(list.Count, iIndex);
            list.Insert(iIndex, value);
            return;
        }

        /**********************************************************************************/
        public static void BinarySearchInsertDescending<TSource, TKey>(
            this IList<TSource> list,
            Func<TSource, TKey> func,
            TSource value)
        {
            Comparison<TKey> comparison = new Comparison<TKey>(Comparer<TKey>.Default.Compare);
            TKey key = func(value);

            int iIndex = BinarySearch(list, t => -comparison(func(t), key));
            iIndex = BinarySearch_ConvertResultToInsertionIndex(list.Count, iIndex);
            list.Insert(iIndex, value);
            return;
        }

        #endregion

        /**********************************************************************************/
        public static void BubbleSort<T>(this IList<T> list, Comparison<T> comparison)
        {
            throw new NotImplementedException();
        }

        /**********************************************************************************/
        public static List<T> Copy<T>(this List<T> source)
        {
            return new List<T>(source);
        }

        /**********************************************************************************/
        /// <summary>
        /// Fluent copy, helps you keep from having to remember constructor semantics.
        /// </summary>
        public static ObservableCollection<T> Copy<T>(this ObservableCollection<T> source)
        {
            if (source == null)
                return null;
            else
                return new ObservableCollection<T>(source);
        }

        /**********************************************************************************/
        public static T[] Copy<T>(this T[] source)
        {
            T[] copy = null;
            if (source != null)
            {
                copy = new T[source.Length];
                source.CopyTo(copy, 0);
            }
            return copy;
        }

        /**********************************************************************************/
        /*public static void Extract(this IList source, params int[] indexArray)
        {
            return Extract(source, indexArray as IEnumerable<int>);
        }*/

        /**********************************************************************************/
        /*public static void Extract(this IList source, IEnumerable<int> indices)
        {
            /// .NET 4: indices.ToSortedSet().Reverse()
            foreach (int iIndex in indices.Distinct().Sort((i1, i2) => -i1.CompareTo(i2)))
            {
                T value = source[iIndex];
                source.RemoveAt(iIndex);
                yield return value;
            }

            yield break;
        }*/

        /**********************************************************************************/
        /// <summary>
        /// Removes items from a list and returns them as they are removed.
        /// If you plan on using the returned enumerable of this function in multiple places,
        /// then first convert it to a collection,
        /// otherwise the deletion will be duplicated on the same indices.
        /// </summary>
        public static IEnumerable<T> Extract<T>(this IList<T> source, params int[] indexArray)
        {
            return Extract(source, indexArray as IEnumerable<int>);
        }

        /**********************************************************************************/
        /// <summary>
        /// Removes items from a list and returns them as they are removed.
        /// If you plan on using the returned enumerable of this function in multiple places,
        /// then first convert it to a collection,
        /// otherwise the deletion will be duplicated on the same indices.
        /// </summary>
        public static IEnumerable<T> Extract<T>(this IList<T> source, IEnumerable<int> indices)
        {
            /// .NET 4: indices.ToSortedSet().Reverse()
            foreach (int iIndex in indices.Distinct().OrderByDescending())
            {
                T value = source[iIndex];
                source.RemoveAt(iIndex);
                yield return value;
            }

            yield break;
        }

        /**********************************************************************************/
        /// <summary>
        /// Removes items from a list and returns them as they are removed.
        /// If you plan on using the returned enumerable of this function in multiple places,
        /// then first convert it to a collection,
        /// otherwise the deletion will be duplicated on the same indices.
        /// </summary>
        public static IEnumerable<T> Extract<T>(this IList<T> source, Func<T, bool> func)
        {
            for (int iIndex = source.Count - 1; iIndex >= 0; iIndex--)
            {
                if (func(source[iIndex]))
                {
                    T value = source[iIndex];
                    source.RemoveAt(iIndex);
                    yield return value;
                }
            }

            yield break;
        }

        /**********************************************************************************/
        /// <summary>
        /// Iterates through a zero-based list.
        /// </summary>
        public static void ForEach<T>(this IList<T> list, int iStartIndex, int iEndIndex, Action<T, int> action)
        {
            if (iEndIndex == -1)
                iEndIndex = list.Count - 1;

            for (int iIndex = iStartIndex; iIndex <= iEndIndex; iIndex++)
                action(list[iIndex], iIndex);
            return;
        }

        /**********************************************************************************/
        public static void HashSort<T>(this IList<T> list, Comparison<T> comparison)
        {
            throw new NotImplementedException();
        }

        /**********************************************************************************/
        public static int IndexOf<T>(this IList<T> list, Func<T, bool> func)
        {
            int iCount = list.Count;
            for (int iIndex = 0; iIndex < iCount; iIndex++)
            {
                if (func(list[iIndex]))
                    return iIndex;
            }

            return -1;
        }

        /**********************************************************************************/
        public static int IndexOf<T>(this T[] array, T value, int iStartIndex, int iCount)
        {
            Func<T, T, bool> comparison = EqualityComparer<T>.Default.Equals;

            for (int iIndex = iStartIndex; iIndex < (iStartIndex + iCount); iIndex++)
            {
                if (comparison(array[iIndex], value))
                    return iIndex;
            }

            return -1;
        }

        /**********************************************************************************/
        public static int IndexOf(this char[] array, char value, int iStartIndex, int iCount)
        {
            for (int iIndex = iStartIndex; iIndex < (iStartIndex + iCount); iIndex++)
            {
                if (array[iIndex] == value)
                    return iIndex;
            }

            return -1;
        }

        /**********************************************************************************/
        public static bool IsNullOrEmpty<T>(this IList<T> list)
        {
            return (list == null) || (list.Count == 0);
        }

        /**********************************************************************************/
        public static bool IsSorted<T>(this IList<T> list, Comparison<T> comparison)
        {
            throw new NotImplementedException();
        }

        /**********************************************************************************/
        /// <summary>
        /// Completely replaces the contents of the IList&lt;T&gt; with those of a provided enumerable,
        /// without destroying the list instance.
        /// This is often preferable to allocating a new IList&lt;T&gt; and reassigning linkages used in databinding.
        /// </summary>
        public static void Overwrite<T>(this IList<T> source, IEnumerable<T> newItems)
        {
            source.Clear();
            AddRange<T>(source, newItems);
            return;
        }

        /**********************************************************************************/
        /// <summary>
        /// Matches the contents of an existing list with that of another, without destroying contents that can remain as-is.
        /// This is vitally important when using observable collections with databound UI controls.
        /// </summary>
        public static void Overwrite<TOld, TNew>(
            this IList<TOld> oldList,
            IEnumerable<TNew> newItems,
            Func<TNew, TOld, bool> newEqualsOld,
            Func<TNew, TOld> create,
            Func<TNew, TOld, TOld> transform = null,
            Func<TOld, TOld, bool> oldEqualsOld = null)
        {
            var newList = newItems.AsList();

            if (oldEqualsOld == null)
                oldEqualsOld = EqualityComparer<TOld>.Default.Equals;

            /// Remove everything the old list has that isn't in the new list (iterate backwards for safe removal).
            for (int iOldIndex = oldList.Count - 1; iOldIndex >= 0; iOldIndex--)
            {
                bool bExistsInNew = false;
                for (int iNewIndex = newList.Count - 1; iNewIndex >= 0; iNewIndex--)
                {
                    if (newEqualsOld(newList[iNewIndex], oldList[iOldIndex]))
                    {
                        bExistsInNew = true;
                        if (transform != null)
                        {
                            var modifiedValue = transform(newList[iNewIndex], oldList[iOldIndex]);
                            if (!oldEqualsOld(oldList[iOldIndex], modifiedValue))
                                oldList[iOldIndex] = modifiedValue;
                        }
                        break;
                    }
                }
                if (!bExistsInNew)
                    oldList.RemoveAt(iOldIndex);
            }

            /// Add everything the new list has that isn't in the old list (iterate backwards because of copy/paste!).
            if (create != null)
            {
                for (int iNewIndex = newList.Count - 1; iNewIndex >= 0; iNewIndex--)
                {
                    bool bExistsInOld = false;
                    for (int iOldIndex = oldList.Count - 1; iOldIndex >= 0; iOldIndex--)
                    {
                        if (newEqualsOld(newList[iNewIndex], oldList[iOldIndex]))
                        {
                            bExistsInOld = true;
                            break;
                        }
                    }
                    if (!bExistsInOld)
                        oldList.Add(create(newList[iNewIndex]));
                }
            }

            return;
        }

        /**********************************************************************************/
        public static void QuickSort<T>(this IList<T> list, Comparison<T> comparison)
        {
            throw new NotImplementedException();
        }

        /**********************************************************************************/
        /// <summary>
        /// Matches the functionality built into List&lt;T&gt;.
        /// </summary>
        public static void RemoveAll<T>(this IList source, Func<T, bool> func)
        {
            for (int iIndex = source.Count - 1; iIndex >= 0; iIndex--)
            {
                if (func.Invoke((T)source[iIndex]))
                    source.RemoveAt(iIndex);
            }
            return;
        }

        /**********************************************************************************/
        /// <summary>
        /// Matches the functionality built into List&lt;T&gt;.
        /// </summary>
        public static void RemoveAll<T>(this IList<T> source, Func<T, bool> func)
        {
            for (int iIndex = source.Count - 1; iIndex >= 0; iIndex--)
            {
                if (func.Invoke(source[iIndex]))
                    source.RemoveAt(iIndex);
            }
            return;
        }

        /**********************************************************************************/
        /*public static void RemoveAt(this IList source, params int[] indexArray)
        {
            RemoveAt(source, indexArray as IEnumerable<int>);
        }*/

        /**********************************************************************************/
        /*public static void RemoveAt(this IList source, IEnumerable<int> indices)
        {
            foreach (int iIndex in indices.ToHashSet().Reverse())
                source.RemoveAt(iIndex);
            return;
        }*/

        /**********************************************************************************/
        public static void RemoveAt<T>(this IList<T> source, params int[] indexArray)
        {
            RemoveAt<T>(source, indexArray as IEnumerable<int>);
            return;
        }

        /**********************************************************************************/
        public static void RemoveAt<T>(this IList<T> source, IEnumerable<int> indices)
        {
            /// .NET 4: indices.ToSortedSet().Reverse()
            foreach (int iIndex in indices.Distinct().OrderByDescending())
                source.RemoveAt(iIndex);
            return;
        }

        /**********************************************************************************/
        public static void Swap<T>(this IList<T> list, int iPosition1, int iPosition2)
        {
            if (iPosition1 != iPosition2)
            {
                if (iPosition1 > iPosition2)
                    GeneralUtilities.Swap(ref iPosition1, ref iPosition2);

                T item1 = list[iPosition1];
                T item2 = list[iPosition2];

                /// Remove #2 first because most lists do a backwards array shift from index to end of array.
                list.RemoveAt(iPosition2);
                list.RemoveAt(iPosition1);

                list.Insert(iPosition1, item2);
                list.Insert(iPosition2, item1);
            }

            return;
        }

        /**********************************************************************************/
        public static void Swap<T>(this ObservableCollection<T> list, int iPosition1, int iPosition2)
        {
            if (iPosition1 != iPosition2)
            {
                list.Move(iPosition2, iPosition1);
                list.Move(iPosition1 + 1, iPosition2);
            }

            return;
        }

        /**********************************************************************************/
        private class NonGenericListWrapper<TElement> : IList<TElement>
        {
            private IList _list = null;
            public NonGenericListWrapper(IList list)
            {
                _list = list;
                return;
            }

            public int IndexOf(TElement item)
            {
                return _list.IndexOf(item);
            }

            public void Insert(int index, TElement item)
            {
                _list.Insert(index, item);
                return;
            }

            public void RemoveAt(int index)
            {
                _list.RemoveAt(index);
                return;
            }

            public TElement this[int index]
            {
                get
                {
                    return (TElement)_list[index];
                }
                set
                {
                    _list[index] = value;
                }
            }

            public void Add(TElement item)
            {
                _list.Add(item);
                return;
            }

            public void Clear()
            {
                _list.Clear();
                return;
            }

            public bool Contains(TElement item)
            {
                return _list.Contains(item);
            }

            public void CopyTo(TElement[] array, int arrayIndex)
            {
                throw new NotImplementedException();
            }

            public int Count
            {
                get { return _list.Count; }
            }

            public bool IsReadOnly
            {
                get { return _list.IsReadOnly; }
            }

            public bool Remove(TElement item)
            {
                bool bExists = _list.Contains(item);
                if (bExists)
                    _list.Remove(item);
                return bExists;
            }

            public IEnumerator<TElement> GetEnumerator()
            {
                foreach (TElement element in _list)
                    yield return element;
            }

            IEnumerator IEnumerable.GetEnumerator()
            {
                return _list.GetEnumerator();
            }
        }

        /**********************************************************************************/
        public static IList<TElement> ToGenericListWrapper<TElement>(this IList source)
        {
            if (source == null)
                return null;
            else
                return new NonGenericListWrapper<TElement>(source);
        }
    }
}
